package java学习.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author 刘世锦
 * 2022-11-19 17:22:53	 当前时间
 */
//给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [1,null,2,3]
//输出：[3,2,1]
// 
//
// 示例 2： 
//
// 
//输入：root = []
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：root = [1]
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数目在范围 [0, 100] 内 
// -100 <= Node.val <= 100 
// 
//
// 
//
// 进阶：递归算法很简单，你可以通过迭代算法完成吗？ 
// Related Topics 栈 树 深度优先搜索 二叉树 
// 👍 946 👎 0

public class 二叉树的后序遍历{
	public static void main(String[] args) {
		Solution solution = new 二叉树的后序遍历().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
	/**
	 * 后序 左右中
	 * 1. stack 按照先序方式 push | 左 右
	 *                         |中
	 * 2. 将需要pop的元素 放入另一栈中
	 * 3. 如此形成 中右左；
	 * 4. 再全部pop；
	 *
	 * | 1 2
	 * | 5 6 4 2 1
	 *  1 2 4 6 5
	 */
//	继先序之法、加以变之
    public List<Integer> postorderTraversal(TreeNode root) {
		ArrayList<Integer> list = new ArrayList<>();
		Stack<TreeNode> stack = new Stack<>();
		Stack<TreeNode> stack1 = new Stack<>();
		if (root==null){
			return list;
		}else {
			stack.push(root);
			while (!stack.isEmpty()){
				TreeNode node = stack.pop();
				stack1.push(node);
				if (node.left!=null){
					stack.push(node.left);
				}
				if (node.right!=null){
					stack.push(node.right);
				}
			}
			while (!stack1.isEmpty()){
				list.add(stack1.pop().val);
			}
//		|
//		|  5 6 4 2 1
//		   1 2 4 6 5


		}
		return list;

	}
}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode() {}
		TreeNode(int val) { this.val = val; }
		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

//leetcode submit region end(Prohibit modification and deletion)

}
